
/*
    739. 每日温度
    优化：用单调栈来解决，维护一个递减的单调栈
    当入栈元素大于栈顶元素时，栈顶元素的升温日即为入栈元素，循环上述过程
 */

public class DailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int max = temperatures[length - 1];
        int min = temperatures[length - 1];
        int[] ans = new int[length];
        ans[length - 1] = 0;
        int index = length - 1;
        for (int i = length - 2; i >= 0; i--) {
            if (temperatures[i] < max && temperatures[i] >= min) {
                for (int j = i + 1; j <= index; j++) {
                    if (temperatures[j] > temperatures[i]) {
                        ans[i] = j - i;
                        break;
                    }
                }
            } else if (temperatures[i] < min) {
                ans[i] = 1;
                min = temperatures[i];
            } else {
                ans[i] = 0;
                max = temperatures[i];
                index = i;
            }
        }
        return ans;
    }
}
